Language/OS - Multiplatform Resource Library/LANGUAGE OS.iso/cpp_libs/intrvews/xgrab.lha/xgrab/ui/pexec.c

C/C++ Source or Header | 1990-03-06 | 51KB | 2,433 lines

/**
   GRAB Graph Layout and Browser System

   Copyright (c) 1989, Tera Computer Company
 **/

  /**
     Execute predicates.  Predicates are executed directly from the
     parse tree, which means semantic checking is done multiple times
     on some pieces, maybe never on others.
   **/

#include <string.h>
#include "attribute.h"
#include "digraph.h"
#include "pexec.h"
#include "token.h"
#include "pparse.h"
#include "globals.h"

BOOL exec_error;
static BOOL pchanged, playout, pnewattr, pfocus;
static BOOL pbroken, pcontinued;
  /* indication of a 'break' or 'continue' command */
static NODE *foc_node;

DIGRAPH *copy_digraph();
LELEMENT *all_nodes_edges();
char *get_val(), *get_nattr_val(), *get_eattr_val();
BOOL get_bool_val();
BOOL check_true(), check_equal();
LELEMENT *get_elem();
LELEMENT *find_elem(), *find_relative();
LELEMENT *get_elems(), *find_relatives();
LELEMENT *get_inedges(), *get_outedges(), *get_parents(), *get_children();
LELEMENT *get_ancestors(), *get_descendants();
LELEMENT *get_source(), *get_sink();
LELEMENT *oedges(), *iedges();
BRUSH string_to_brush();
SHAPE string_to_shape();
COLOR string_to_color();
char *shape_to_string(), *color_to_string(), *brush_to_string();
char *bool_to_string();
OUTEDGE *get_edge();
NODE *visual();
char *UniqueName();

typedef LELEMENT * (*PFT1)();
typedef LELEMENT * (*PFT2)();

  /* node relative functions */
PFT1 nrelfn [NUM_NREL] =
{
    get_inedges,
    get_outedges,
    get_parents,
    get_children,
    get_ancestors,
    get_descendants
};

  /* edge relative functions */
PFT2 erelfn[NUM_EREL] =
{
    get_source,
    get_sink
};

dispose_ptree(tree)
PTREE *tree;
{
    if (tree != NULL)
    {
        dispose_ptree(tree->left);
    dispose_ptree(tree->right);

    if (tree->val != NULL)
    {
        dispose(tree->val);
    }

    dispose(tree);
    }
}

exec_commands(commands, err, changed, relayout, newattr, focus, fnode)
PTREE *commands;
BOOL *err, *changed, *relayout, *newattr, *focus;
NODE **fnode;
  /**
     Execute the top-level list of commands.
     When done, err is TRUE if there was an error.
        changed is TRUE if the graph was changed
        relayout is TRUE if the graph needs to be relayedout
        newattr is TRUE if a new attribute was added
        focus is TRUE if a node was focussed to
        fnode is the node to focus to
   **/
{
    DIGRAPH *save, *tmp;  /* in case things fail */
    LELEMENT *elems, *list;
      /* the list of things to execute the commands upon, and a copy of it */

    pchanged = FALSE;
    playout = FALSE;
    pnewattr = FALSE;
    pfocus = FALSE;
    *fnode = NULL;
    exec_error = FALSE;
    pbroken = FALSE;
    tmp = copy_digraph(digraph);
    save = digraph;
    digraph = tmp;

    for (elems = all_nodes_edges(digraph), list = elems; elems != NULL;
     elems = elems->next)
    {
    pcontinued = FALSE;
    exec_command_list(commands, digraph, elems);

    if (exec_error)
    {
        goto resave;
    }
    else if (pbroken)
    {
        break;
    }
    }

    *err = FALSE;
    *changed = pchanged;
    *relayout = playout;
    *newattr = pnewattr;
    *focus = pfocus;
    *fnode = foc_node;

    dispose_lelem_list(list);

    if (pchanged)
    {
    dispose_digraph(save);
    }
    else     /* no change, so keep the old digraph */
    {
    dispose_digraph(digraph);
    digraph = save;
    }

    return;

resave:
    fprintf(stderr, "Old digraph retained.\n");
    dispose_digraph(digraph);
    digraph = save;
    *changed = FALSE;
    *relayout = FALSE;
    *newattr = FALSE;
    *err = TRUE;
    *focus = FALSE;
    *fnode = NULL;

    dispose_lelem_list(list);
    return;
}

dispose_lelem_list(l)
LELEMENT *l;
{
    LELEMENT *next;

    while (l != NULL)
    {
    next = l->next;
    dispose(l);
    l = next;
    }
}

exec_command_list(command, digraph, current)
PTREE *command;
DIGRAPH *digraph;
LELEMENT *current;
  /**
     execute the commands in command on digraph digraph, where current is the
     current node.
   **/
{
    PTREE *currcommand;
    NODE *to;

    for (currcommand = command; currcommand != NULL;
         currcommand = currcommand->right)
    {
    if (!current->node)
      /* find the destination if it's an outedge */
    {
        to = visual(digraph,
            Node(digraph, To_vno((OUTEDGE *) current->gelement)));
    }

    if (ignoreHidden &&
        (current->node && !Displayed((NODE *) current->gelement)) ||
        (!current->node &&
         (!Displayed(current->from) || !Displayed(to))))
      /* stop processing if the node or edge has become hidden */
    {
        break;
    }

        if (currcommand->token != SEMICOLON_TOKEN)
        {
            exec_error = TRUE;
        print_ln(currcommand->lineno);
        print_cl(current);
        fprintf(stderr, "exec_command_lists: not a command list ");
        print_token(currcommand->token, TRUE);
        return;
    }
    else
    {
        exec_command(currcommand->left, digraph, current);
        exec_ck;
    }
    }
}

exec_command(command, digraph, current)
PTREE *command;
DIGRAPH *digraph;
LELEMENT *current;
{
    exec_ck;

    if (command != NULL)    /* a superfluous semicolon could cause this */
    {
    switch (command->token)
    {
        case IF_TOKEN:
        exec_if_or_elsifstmt(command, digraph, current);
        break;
        case SET_TOKEN:
        exec_setstmt(command, digraph, current);
        break;
        case COALESCE_TOKEN:
        exec_coalescestmt(command, digraph, current);
        break;
        case EXPAND_TOKEN:
        exec_expandstmt(command, digraph, current);
        break;
        case HIDE_TOKEN:
        exec_hidestmt(command, digraph, current);
        break;
        case DISPLAY_TOKEN:
        exec_displaystmt(command, digraph, current);
        break;
        case FOCUS_TOKEN:
        exec_focusstmt(command, digraph, current);
        break;
        case BREAK_TOKEN:
        pbroken = TRUE;
        break;
        case CONTINUE_TOKEN:
        pcontinued = TRUE;
        break;
        default:
        exec_error = TRUE;
            print_ln(command->lineno);
            print_cl(current);
        fprintf(stderr, "exec_command: not a valid command");
        print_token(command->token, TRUE);
        break;
    }
    }
}

exec_focusstmt(command, digraph, current)
PTREE *command;
DIGRAPH *digraph;
LELEMENT *current;
{
    PTREE *rest;
    LELEMENT *elems;

    exec_ck;

    if (command == NULL)
    {
    exec_error = TRUE;
    print_cl(current);
    fprintf(stderr, "node tree empty\n");
    return;
    }
    else if (command->token != FOCUS_TOKEN)
    {
    exec_error = TRUE;
    print_ln(command->lineno);
    print_cl(current);
    fprintf(stderr, "focus tree can't be rooted with ");
    print_token(command->token, TRUE);
    return;
    }
    else if (command->right != NULL)
    {
    exec_error = TRUE;
    print_ln(command->lineno);
    print_cl(current);
    fprintf(stderr, "focus tree must have empty right child.\n");
    return;
    }
    else
    {
    elems = get_elems(command->left, digraph, current, &rest);
    exec_ck;

    if (rest != NULL)
    {
        exec_error = TRUE;
        print_ln(rest->lineno);
        print_cl(current);
        fprintf(stderr, "right child of focus node tree must be empty.\n");
        return;
    }
    else
    {
        for (; elems != NULL; elems = elems->next)
        {
        if (!elems->node)
        {
                exec_error = TRUE;
                print_ln(command->lineno);
                print_cl(current);
                fprintf(stderr,
                "Target of focus command must be a node.\n");
                return;
        }
            else
            {
            pfocus = TRUE;
            foc_node = (NODE *) elems->gelement;
        }
        }
    }
    }
}

exec_hidestmt(command, digraph, current)
PTREE *command;
DIGRAPH *digraph;
LELEMENT *current;
  /**
     after a hide, the succ/ante sets must be changed.  This routine
     doesn't change them.  The graph had better be relayed out, which will
     fix the sets
   **/
{
    PTREE *rest;
    LELEMENT *elems;

    exec_ck;

    if (command == NULL)
    {
    exec_error = TRUE;
    print_cl(current);
    fprintf(stderr, "node tree empty\n");
    return;
    }
    else if (command->token != HIDE_TOKEN)
    {
    exec_error = TRUE;
    print_ln(command->lineno);
    print_cl(current);
    fprintf(stderr, "hide tree can't be rooted with ");
    print_token(command->token, TRUE);
    return;
    }
    else if (command->right != NULL)
    {
    exec_error = TRUE;
    print_ln(command->lineno);
    print_cl(current);
    fprintf(stderr, "hide tree must have empty right child.\n");
    return;
    }
    else
    {
    elems = get_elems(command->left, digraph, current, &rest);
    exec_ck;

    if (rest != NULL)
    {
        exec_error = TRUE;
        print_ln(rest->lineno);
        print_cl(current);
        fprintf(stderr, "right child of hide node tree must be empty.\n");
        return;
    }
    else
    {
        for (; elems != NULL; elems = elems->next)
        {
        if (!elems->node)
        {
                exec_error = TRUE;
                print_ln(command->lineno);
                print_cl(current);
                fprintf(stderr, "Target of hide command must be a node.\n");
                return;
        }
            else
            {
                Displayed((NODE *) (elems->gelement)) = FALSE;
                playout = TRUE;
                pchanged = TRUE;
        }
        }
    }
    }
}

exec_displaystmt(command, digraph, current)
PTREE *command;
DIGRAPH *digraph;
LELEMENT *current;
  /**
     After a display, the ante/succ sets must be changed, and this routine
     doesn't change them.  The graph had better be relayed out, which will
     cause the sets to be fixed.
   **/
{
    PTREE *rest;
    LELEMENT *elems;

    exec_ck;

    if (command == NULL)
    {
    exec_error = TRUE;
    print_cl(current);
    fprintf(stderr, "node tree empty\n");
    return;
    }
    else if (command->token != DISPLAY_TOKEN)
    {
    exec_error = TRUE;
    print_ln(command->lineno);
    print_cl(current);
    fprintf(stderr, "display tree can't be rooted with ");
    print_token(command->token, TRUE);
    return;
    }
    else if (command->right != NULL)
    {
    exec_error = TRUE;
    print_ln(command->lineno);
    print_cl(current);
    fprintf(stderr, "display tree must have empty right child.\n");
    return;
    }
    else
    {
    elems = get_elems(command->left, digraph, current, &rest);
    exec_ck;

    if (rest != NULL)
    {
        exec_error = TRUE;
        print_ln(rest->lineno);
        print_cl(current);
        fprintf(stderr,
            "right child of display node tree must be empty.\n");
        return;
    }
    else
    {
        for (; elems != NULL; elems = elems->next)
        {
        if (!elems->node)
        {
                exec_error = TRUE;
                print_ln(command->lineno);
                print_cl(current);
                fprintf(stderr,
                "Target of display command must be a node.\n");
                return;
        }
            else
            {
                Displayed((NODE *) (elems->gelement)) = TRUE;
                playout = TRUE;
                pchanged = TRUE;
            }
        }
    }
    }
}

exec_coalescestmt(command, digraph, current)
PTREE *command;
DIGRAPH *digraph;
LELEMENT *current;
{
    PTREE *rest;
    LELEMENT *elems;
    LELEMENT *elem;

    exec_ck;

    if (command == NULL)
    {
    exec_error = TRUE;
    print_cl(current);
    fprintf(stderr, "node tree empty\n");
    return;
    }
    else if (command->token != COALESCE_TOKEN)
    {
    exec_error = TRUE;
    print_ln(command->lineno);
    print_cl(current);
    fprintf(stderr, "coalesce tree can't be rooted with ");
    print_token(command->token, TRUE);
    return;
    }
    else
    {
    elems = get_elems(command->left, digraph, current, &rest);
    exec_ck;

    if (rest != NULL)
    {
        exec_error = TRUE;
        print_ln(rest->lineno);
        print_cl(current);
        fprintf(stderr,
            "right child of first coalesce node tree must be empty.\n");
        return;
    }

    elem = get_elem(command->right, digraph, current, &rest);
    exec_ck;

    if (rest != NULL)
    {
        exec_error = TRUE;
        print_ln(rest->lineno);
        print_cl(current);
        fprintf(stderr, "right child of second coalesce node tree must be empty.\n");
        return;
    }
    else
    {
        if (!elem->node)
        {
        exec_error = TRUE;
        print_ln(command->lineno);
        print_cl(current);
        fprintf(stderr, "Second coalesce argument must be a node.\n");
        return;
        }
        else
        {
          /**
             first off, get a coalesced node.  We do this by
             coalescing the node with itself (which does nothing if
             the node is already coalesced.  If it isn't, it creates
             a new coalesced node.  Find the new node by using
             find_elem
           **/
        coalesce(digraph, (NODE *) elem->gelement,
             (NODE *) elem->gelement);
        elem = find_elem(Text((NODE *) elem->gelement), digraph,
                    command->lineno, current);

          /**
             now coalesce the set of nodes with this one
           **/
            for (; elems != NULL; elems = elems->next)
            {
                if (!elems->node)
            {
                    exec_error = TRUE;
                    print_ln(command->lineno);
                    print_cl(current);
                    fprintf(stderr, "First coalesce argument must be a set of nodes.\n");
                    return;
            }
                else
                {
                coalesce(digraph,
                 (NODE *) elems->gelement,
                 (NODE *) elem->gelement);
                    playout = TRUE;
                    pchanged = TRUE;
            }
            }
        }
    }
    }
}

exec_expandstmt(command, digraph, current)
PTREE *command;
DIGRAPH *digraph;
LELEMENT *current;
{
    PTREE *rest;
    LELEMENT *elems;

    exec_ck;

    if (command == NULL)
    {
    exec_error = TRUE;
    print_cl(current);
    fprintf(stderr, "node tree empty\n");
    return;
    }
    else if (command->token != EXPAND_TOKEN)
    {
    exec_error = TRUE;
    print_ln(command->lineno);
    print_cl(current);
    fprintf(stderr, "expand tree can't be rooted with ");
    print_token(command->token, TRUE);
    return;
    }
    else if (command->right != NULL)
    {
    exec_error = TRUE;
    print_ln(command->lineno);
    print_cl(current);
    fprintf(stderr, "expand tree must have empty right child.\n");
    return;
    }
    else
    {
    elems = get_elems(command->left, digraph, current, &rest);
    exec_ck;

    if (rest != NULL)
    {
        exec_error = TRUE;
        print_ln(rest->lineno);
        print_cl(current);
        fprintf(stderr,
            "right child of expand node tree must be empty.\n");
        return;
    }
    else
    {
        for (; elems != NULL; elems = elems->next)
        {
            if (!elems->node)
        {
                exec_error = TRUE;
                print_ln(command->lineno);
                print_cl(current);
                fprintf(stderr,
                "Target of expand command must be a node.\n");
                return;
        }
            else
            {
                if (!Coalescer((NODE *) elems->gelement))
                {
print_ln(command->left->lineno);
print_cl(current);
fprintf(stderr, "warning: expand on a non-coalescer node\n");
            }
            else
            {
                expand(digraph, (NODE *) elems->gelement);
                    playout = TRUE;
                    pchanged = TRUE;
            }
            }
        }
    }
    }
}

exec_setstmt(command, digraph, current)
PTREE *command;
DIGRAPH *digraph;
LELEMENT *current;
{
    char *val;

    exec_ck;

    val = get_val(command->right, digraph, current);
    set_attrs(command->left, digraph, current, val);
}

exec_if_or_elsifstmt(command, digraph, current)
PTREE *command;
DIGRAPH *digraph;
LELEMENT *current;
{
    BOOL val;

    exec_ck;

    if (command == NULL)
      /* end of if-elsif chain; no else statement */
    {
    return;
    }
    else if (command->token == SEMICOLON_TOKEN)
      /* else statement: command list */
    {
    exec_command_list(command, digraph, current);
    }
    else if (command->left == NULL)
    {
    exec_error = TRUE;
    print_ln(command->lineno);
    print_cl(current);
    fprintf(stderr, "exec_if_or_elsifstmt: empty then tree\n");
    return;
    }
    else if (command->left->token != THEN_TOKEN)
    {
    exec_error = TRUE;
    print_ln(command->left->lineno);
    print_cl(current);
    fprintf(stderr, "exec_ifstmt: then tree can't be rooted with ");
    print_token(command->left->token, TRUE);
    return;
    }
    else
    {
    val = check_true(command->left->left, digraph, current);
    exec_ck;

        if (val)
    {
            exec_command_list(command->left->right, digraph, current);
    }
    else
    {
        exec_if_or_elsifstmt(command->right, digraph, current);
    }
    }
}

BOOL check_true(bexpr, digraph, current)
PTREE *bexpr;
DIGRAPH *digraph;
LELEMENT *current;
{
    exec_ckb;

    if (bexpr == NULL)
    {
    exec_error = TRUE;
    print_cl(current);
    fprintf(stderr, "boolean expression tree empty.\n");
    return FALSE;
    }
    else
    {
    BOOL val;

    switch (bexpr->token)
    {
        case AND_TOKEN:
        val = check_true(bexpr->left, digraph, current);
        exec_ckb;

        return (val && check_true(bexpr->right, digraph, current));

        case OR_TOKEN:
        val = check_true(bexpr->left, digraph, current);
        exec_ckb;

        return (val || check_true(bexpr->right, digraph, current));

        case NOT_TOKEN:
        return !check_true(bexpr->left, digraph, current);

        case EQUAL_TOKEN:
          /**
             EQUAL_TOKEN stands for two types of expressions:
            expr        (return TRUE if expr TRUE)
            expr = expr    (return TRUE if expr = expr)
             the former is indicated if the right child is NULL
           **/
        if (bexpr->right == NULL)
        {
            return get_bool_val(bexpr->left, digraph, current);
        }
        else
        {
            return check_equal(bexpr->left, bexpr->right, digraph,
                       current);
        }
        default:
        exec_error = TRUE;
        print_ln(bexpr->lineno);
        print_cl(current);
        fprintf(stderr,
            "boolean expression tree cannot be rooted with ");
        print_token(bexpr->token, TRUE);
        return FALSE;
    }
    }
}

BOOL check_equal(e1, e2, digraph, current)
PTREE *e1, *e2;
DIGRAPH *digraph;
LELEMENT *current;
{
    char *s1, *s2;

    exec_ckb;

    s1 = get_val(e1, digraph, current);
    exec_ckb;

    s2 = get_val(e2, digraph, current);
    exec_ckb;

    if (!strcmp(s1, s2))
    {
    return TRUE;
    }
    else
    {
    return FALSE;
    }
}

set_attrs(lval, digraph, current, val)
PTREE *lval;
DIGRAPH *digraph;
LELEMENT *current;
char *val;
  /**
     Set the attribute(s) (could be more than one) indicated by lval to val
   **/
{
    PTREE *rest;
    LELEMENT *elems;

    exec_ck;

    if (lval == NULL)
    {
    exec_error = TRUE;
    print_cl(current);
    fprintf(stderr, "lvalue tree empty\n");
    return;
    }
    else
    {
    elems = get_elems(lval, digraph, current, &rest);
    exec_ck;

    for (; elems != NULL; elems = elems->next)
    {
        if (elems->node)
        {
            set_nattr(digraph, (NODE *) (elems->gelement), rest, current,
              val);
        exec_ck;
        }
        else
        {
            set_eattr(digraph, (OUTEDGE *) (elems->gelement), rest,
              current, val);
        exec_ck;
        }
    }
    }
}

char *get_val(rval, digraph, current)
PTREE *rval;
DIGRAPH *digraph;
LELEMENT *current;
{
    PTREE *rest;
    LELEMENT *elem;

    exec_ckp;

    if (rval == NULL)
    {
    exec_error = TRUE;
    print_cl(current);
    fprintf(stderr, "rvalue tree empty\n");
    return NULL;
    }
    else if (rval->token == QSTRING_TOKEN)
      /* quoted strings indicate literal values */
    {
    return rval->val;
    }
    else
    {
        elem = get_elem(rval, digraph, current, &rest);
    exec_ckp;

    if (elem->node)
    {
        return get_nattr_val(digraph, (NODE *) (elem->gelement), rest,
                 current);
    }
    else
    {
        return get_eattr_val(digraph, (OUTEDGE *) (elem->gelement), rest,
                 current);
    }
    }
}

LELEMENT *get_elem(tree, digraph, current, rest)
PTREE *tree;
DIGRAPH *digraph;
LELEMENT *current;
PTREE **rest;
  /* get *one* element of the graph indicated by tree */
{
    LELEMENT *curr, *tmp;

    exec_ckp;

    if (tree == NULL)
    {
        exec_error = TRUE;
    print_cl(current);
        fprintf(stderr, "node or edge designator tree empty.\n");
        return NULL;
    }
    else if (tree->token != PERIOD_TOKEN)
    {
    exec_error = TRUE;
    print_ln(tree->lineno);
    print_cl(current);
    fprintf(stderr, "node or edge designator tree can't be rooted with ");
    print_token(tree->token, TRUE);
    return NULL;
    }
    else if (tree->left == NULL)
      /* start at current node */
    {
    new(curr, LELEMENT);
    curr->node = current->node;
    curr->gelement = current->gelement;
    curr->from = current->from;
    curr->next = NULL;
    }
    else if (tree->left->token != QSTRING_TOKEN)
    {
    exec_error = TRUE;
    print_ln(tree->left->lineno);
    print_cl(current);
    fprintf(stderr, "attribute designator tree can't be rooted with ");
    print_token(tree->left->token, TRUE);
    return NULL;;
    }
    else
    {
    curr = find_elem(tree->left->val, digraph, tree->left->lineno, current);
    }

    for (tree = tree->right; tree != NULL && tree->token == PERIOD_TOKEN;
     tree = tree->right)
    {
    tmp = find_relative(curr, tree->left, digraph, current);
      dispose(curr);
    curr = tmp;
    exec_ckp;
    }

    *rest = tree;

    return curr;
}

LELEMENT *find_relative(curr, tree, digraph, current)
LELEMENT *curr;
PTREE *tree;
DIGRAPH *digraph;
LELEMENT *current;
  /* find *one* relative of curr indicated by tree */
{
    char *s;
    LELEMENT *relatives;

    exec_ckp;

    if (tree == NULL)
    {
    exec_error = TRUE;
    print_cl(current);
    fprintf(stderr, "attribute designator tree is empty\n");
    return NULL;
    }
    else
    {
    switch (tree->token)
    {
        case STRING_TOKEN:
        if (curr->node)
        {
                s = get_nattr_val(digraph, (NODE *) (curr->gelement),
                      tree, current);
            exec_ckp;
            }
        else
        {
                s = get_eattr_val(digraph, (OUTEDGE *) (curr->gelement),
                      tree, current);
            exec_ckp;
            }

        return find_elem(s, digraph, tree->lineno, current);

        case IN_TOKEN:
        case OUT_TOKEN:
        case PARENTS_TOKEN:
        case CHILDREN_TOKEN:
        case ANCESTORS_TOKEN:
        case DESCENDANTS_TOKEN:
        if (!curr->node)
        {
            exec_error = TRUE;
            print_ln(tree->lineno);
            print_cl(current);
            fprintf(stderr, "target of %s attribute not a node\n",
                reserved_wd[(int) tree->token -
                    (int) FIRST_RESERVED_TOKEN]);
            return NULL;
        }
        else
        {
            relatives =
              nrelfn[(int) tree->token -
                 (int) FIRST_NREL_TOKEN]((NODE *) (curr->gelement),
                             digraph);

            if (relatives == NULL)
            {
            exec_error = TRUE;
                print_ln(tree->lineno);
                print_cl(current);
            fprintf(stderr, "%s attribute yields empty set\n",
                    reserved_wd[(int) tree->token -
                        (int) FIRST_RESERVED_TOKEN]);
            return NULL;
            }
            else if (relatives->next != NULL)
            {
            exec_error = TRUE;
                print_ln(tree->lineno);
                print_cl(current);
            fprintf(stderr, "%s attribute result ambiguous\n",
                    reserved_wd[(int) tree->token -
                        (int) FIRST_RESERVED_TOKEN]);
            dispose_lelem_list(relatives);
            return NULL;
            }
            else
            {
            return relatives;
            }
        }

        case SOURCE_TOKEN:
        case SINK_TOKEN:
        if (curr->node)
        {
            exec_error = TRUE;
            print_ln(tree->lineno);
            print_cl(current);
            fprintf(stderr, "target of %s attribute not an edge\n",
                reserved_wd[(int) tree->token -
                    (int) FIRST_RESERVED_TOKEN]);
            return NULL;
        }
        else
        {
            relatives =
              erelfn[(int) tree->token -
                 (int) FIRST_EREL_TOKEN](
                   (OUTEDGE *) (curr->gelement), digraph,
                   curr->from);

            if (relatives == NULL)
            {
            exec_error = TRUE;
                print_ln(tree->lineno);
                print_cl(current);
            fprintf(stderr, "%s attribute yields empty set\n",
                    reserved_wd[(int) tree->token -
                        (int) FIRST_RESERVED_TOKEN]);
            return NULL;
            }
            else if (relatives->next != NULL)
            {
            exec_error = TRUE;
                print_ln(tree->lineno);
                print_cl(current);
            fprintf(stderr, "%s attribute result ambiguous\n",
                    reserved_wd[(int) tree->token -
                        (int) FIRST_RESERVED_TOKEN]);
            dispose_lelem_list(relatives);
            return NULL;
            }
            else
            {
            return relatives;
            }
        }

        default:
        exec_error = TRUE;
        print_ln(tree->lineno);
        print_cl(current);
        fprintf(stderr,
            "attribute designator tree can't be rooted with ");
        print_token(tree->token, TRUE);
        return NULL;
    }
    }
}

LELEMENT *find_elem(s, digraph, lineno, current)
char *s;
DIGRAPH *digraph;
int lineno;
LELEMENT *current;
  /**
     find and return the first element in the digraph with distinguished
     attribute equal to s.
   **/
{
    NODE *node;
    LELEMENT *result, *p;

    exec_ckp;

    each_pred_node(digraph, node)
    loop
    if (Is_dummy(node))
    {
        continue;
    }

    if (!strcmp(s, Text(node)))
    {
        new(result, LELEMENT);
        result->node = TRUE;
            result->from = NULL;
        result->gelement = (GELEMENT) node;
        result->next = NULL;
        return result;
    }
    else
    {
        result = oedges(digraph, node);

        for (; result != NULL; result = p)
        {
        if (!strcmp(s, Label((OUTEDGE *) result->gelement)))
        {
            dispose_lelem_list(result->next);
            result->next = NULL;
            return result;
        }
        else
        {
            p = result->next;
            dispose(result);
        }
        }
    }
    endloop;

    exec_error = TRUE;
    print_ln(lineno);
    print_cl(current);
    fprintf (stderr, "Couldn't find node or edge with label %s\n", s);
    return NULL;
}

LELEMENT *get_elems(tree, digraph, current, rest)
PTREE *tree;
DIGRAPH *digraph;
LELEMENT *current;
PTREE **rest;
  /**
     find the element(s) (>=0 of them) indicated by tree
   **/
{
    LELEMENT *curr, *tmp;

    exec_ckp;

    if (tree == NULL)
    {
        exec_error = TRUE;
    print_cl(current);
        fprintf(stderr, "node or edge designator tree empty.\n");
        return NULL;
    }
    else if (tree->token != PERIOD_TOKEN)
    {
    exec_error = TRUE;
    print_ln(tree->lineno);
    print_cl(current);
    fprintf(stderr, "node or edge designator tree can't be rooted with ");
    print_token(tree->token, TRUE);
    return NULL;
    }
    else if (tree->left == NULL)
      /* start at current node */
    {
    new(curr, LELEMENT);
    curr->node = current->node;
    curr->gelement = current->gelement;
    curr->from = current->from;
    curr->next = NULL;
    }
    else if (tree->left->token != QSTRING_TOKEN)
    {
    exec_error = TRUE;
    print_ln(tree->left->lineno);
    print_cl(current);
    fprintf(stderr, "attribute designator tree can't be rooted with ");
    print_token(tree->left->token, TRUE);
    return NULL;
    }
    else
    {
    curr = find_elem(tree->left->val, digraph, tree->left->lineno,
              current);
    }

    for (tree = tree->right; tree != NULL && tree->token == PERIOD_TOKEN;
     tree = tree->right)
    {
    tmp = find_relatives(curr, tree->left, digraph, current);
    dispose_lelem_list(curr);
    curr = tmp;
    exec_ckp;
    }

    *rest = tree;
    return curr;
}

LELEMENT *find_relatives(curr, tree, digraph, current)
LELEMENT *curr;
PTREE *tree;
DIGRAPH *digraph;
LELEMENT *current;
  /**
     find the relative(s) (>= 0) of curr indicated by tree
   **/
{
    char *s;
    LELEMENT *relatives, *head;

    exec_ckp;

    if (tree == NULL)
    {
    exec_error = TRUE;
    print_cl(current);
    fprintf(stderr, "attribute designator tree is empty\n");
    return NULL;
    }

    for (head = NULL; curr != NULL; curr = curr->next)
    {
    switch (tree->token)
    {
        case STRING_TOKEN:
        if (curr->node)
        {
                s = get_nattr_val(digraph, (NODE *) (curr->gelement),
                      tree, current);
            exec_ckp;
            }
        else
        {
                s = get_eattr_val(digraph, (OUTEDGE *) (curr->gelement),
                      tree, current);
            exec_ckp;
            }

        relatives = find_elem(s, digraph, tree->lineno, current);
        break;

        case IN_TOKEN:
        case OUT_TOKEN:
        case PARENTS_TOKEN:
        case CHILDREN_TOKEN:
        case ANCESTORS_TOKEN:
        case DESCENDANTS_TOKEN:
        if (!curr->node)
        {
            exec_error = TRUE;
            print_ln(tree->lineno);
            print_cl(current);
            fprintf(stderr, "target of %s attribute not a node\n",
                reserved_wd[(int) tree->token -
                    (int) FIRST_RESERVED_TOKEN]);
            return NULL;
        }
        else
        {
            relatives =
              nrelfn[(int) tree->token -
                 (int) FIRST_NREL_TOKEN]((NODE *) (curr->gelement),
                             digraph);
            break;
        }

        case SOURCE_TOKEN:
        case SINK_TOKEN:
        if (curr->node)
        {
            exec_error = TRUE;
            print_ln(tree->lineno);
            print_cl(current);
            fprintf(stderr, "target of %s attribute not an edge\n",
                reserved_wd[(int) tree->token -
                    (int) FIRST_RESERVED_TOKEN]);
            return NULL;
        }
        else
        {
            relatives =
              erelfn[(int) tree->token -
                 (int) FIRST_EREL_TOKEN](
                (OUTEDGE *) (curr->gelement), digraph,
                curr->from);
            break;
        }

        default:
        exec_error = TRUE;
        print_ln(tree->lineno);
        print_cl(current);
        fprintf(stderr,
            "attribute designator tree can't be rooted with ");
        print_token(tree->token, TRUE);
        return NULL;
    }

    append_list(relatives, &head);
    }

    return head;
}

append_list(list1, list2)
LELEMENT *list1, **list2;
  /**
     add elements of list1 to list2.  Don't add duplicates.
     The discerning reader will note that this procedure isn't very efficient,
     but the lelement lists shouldn't be very long.
   **/
{
    LELEMENT *p, *n;

    for (; list1 != NULL; list1 = n)
    {
    n = list1->next;

    for (p = *list2; p != NULL; p = p->next)
    {
        if (p->gelement == list1->gelement)
        {
        goto next;
        }
    }

    list1->next = *list2;
    *list2 = list1;
next:
    ;
    }
}

append_list_dups(list1, list2)
LELEMENT *list1, **list2;
  /* Much like append_list above, but we'll add duplicates */
{
    LELEMENT *p;

    if (*list2 == NULL)
    {
    *list2 = list1;
    return;
    }

    for (p = *list2; p->next != NULL; p = p->next)
    {
    }

    p->next = list1;
}

set_nattr(digraph, n, tree, current, val)
DIGRAPH *digraph;
NODE *n;
PTREE *tree;
LELEMENT *current;
char *val;
  /**
     set n's value for the attribute represented by the tree.  If the
     attribute doesn't exist, create it for all nodes.
   **/
{
    int i;

    exec_ck;

    if (tree == NULL)
    {
    exec_error = TRUE;
        print_cl(current);
    fprintf(stderr, "Node attribute tree is empty.\n");
    return;
    }
    else
    {
        switch(tree->token)
    {
        case STRING_TOKEN:
        for (i = 0; i < NNodeAttr(digraph); i++)
        {
            if (!strcmp(tree->val, NAttrName(digraph, i)))
            {
            dispose(NAttr(n, i));
            strsave(NAttr(n, i), val);
            pchanged = TRUE;
            return;
            }
        }

print_ln(tree->lineno);
print_cl(current);
fprintf(stderr, "Creating node attribute named %s\n", tree->val);
        create_nattr(digraph, tree->val);
        dispose(NAttr(n, NNodeAttr(digraph) - 1));
        strsave(NAttr(n, NNodeAttr(digraph) - 1), val);
        pnewattr = TRUE;
        break;

        case BRUSH_TOKEN:
        Brush(n) = string_to_brush(tree->val);
        case SHAPE_TOKEN:
        Shape(n) = string_to_shape(tree->val);
        case COLOR_TOKEN:
        Color(n) = string_to_color(tree->val);
        case DISPLAY_TOKEN:
        case COALESCER_TOKEN:
        case NODE_TOKEN:
        case EDGE_TOKEN:
        exec_error = TRUE;
        print_ln(tree->lineno);
        print_cl(current);
        fprintf(stderr, "Cannot set node attribute ");
        print_token(tree->token, TRUE);
        return;
        default:
        exec_error = TRUE;
        print_ln(tree->lineno);
            print_cl(current);
        fprintf(stderr, "Node attribute tree cannot be rooted with ");
        print_token(tree->token, TRUE);
        return;
    }

    pchanged = TRUE;
    }
}

char *get_nattr_val(digraph, n, tree, current)
DIGRAPH *digraph;
NODE *n;
PTREE *tree;
LELEMENT *current;
  /* return n's value for the attribute represented by the tree */
{
    int i;

    exec_ckp;

    if (tree == NULL)
    {
    exec_error = TRUE;
        print_cl(current);
    fprintf(stderr, "Node attribute tree is empty.\n");
    return NULL;
    }
    else
    {
        switch(tree->token)
    {
        case STRING_TOKEN:
        for (i = 0; i < NNodeAttr(digraph); i++)
        {
            if (!strcmp(tree->val, NAttrName(digraph, i)))
            {
            return NAttr(n, i);
            }
        }

        exec_error = TRUE;
        print_ln(tree->lineno);
            print_cl(current);
        fprintf(stderr, "No node attribute named %s\n", tree->val);
        return NULL;
        case BRUSH_TOKEN:
        return brush_to_string(Brush(n));
        case SHAPE_TOKEN:
        return brush_to_string(Shape(n));
        case COLOR_TOKEN:
        return brush_to_string(Color(n));
        case DISPLAY_TOKEN:
        return bool_to_string(Displayed(n));
        case COALESCER_TOKEN:
        return bool_to_string(Coalescer(n));
        case NODE_TOKEN:
        return bool_to_string(TRUE);
        case EDGE_TOKEN:
        return bool_to_string(FALSE);
        default:
        exec_error = TRUE;
        print_ln(tree->lineno);
            print_cl(current);
        fprintf(stderr, "Node attribute tree cannot be rooted with ");
        print_token(tree->token, TRUE);
        return NULL;
    }
    }
}

set_eattr(digraph, e, tree, current, val)
DIGRAPH *digraph;
OUTEDGE *e;
PTREE *tree;
LELEMENT *current;
char *val;
  /**
     set e's value for the attribute represented by the tree.  If the
     attribute doesn't exist, create it for all edges.
   **/
{
    int i;

    exec_ck;

    if (tree == NULL)
    {
    exec_error = TRUE;
        print_cl(current);
    fprintf(stderr, "Edge attribute tree is empty.\n");
    return;
    }
    else
    {
        switch(tree->token)
    {
        case STRING_TOKEN:
        for (i = 0; i < NEdgeAttr(digraph); i++)
        {
            if (!strcmp(tree->val, EAttrName(digraph, i)))
            {
            dispose(EAttr(e, i));
            strsave(EAttr(e, i), val);
            pchanged = TRUE;
            return;
            }
        }

print_ln(tree->lineno);
print_cl(current);
fprintf(stderr, "Creating edge attribute named %s\n", tree->val);
        create_eattr(digraph, tree->val);
        dispose(EAttr(e, NEdgeAttr(digraph) - 1));
        strsave(EAttr(e, NEdgeAttr(digraph) - 1), val);
        pnewattr = TRUE;
        break;

        case BRUSH_TOKEN:
        Brush(e) = string_to_brush(tree->val);
        case COLOR_TOKEN:
        Color(e) = string_to_color(tree->val);
        case NODE_TOKEN:
        case EDGE_TOKEN:
        exec_error = TRUE;
        print_ln(tree->lineno);
        print_cl(current);
        fprintf(stderr, "Cannot set edge attribute ");
        print_token(tree->token, TRUE);
        return;
        default:
        exec_error = TRUE;
        print_ln(tree->lineno);
            print_cl(current);
        fprintf(stderr, "Edge attribute tree cannot be rooted with ");
        print_token(tree->token, TRUE);
        return;
    }

    pchanged = TRUE;
    }
}

char *get_eattr_val(digraph, e, tree, current)
DIGRAPH *digraph;
OUTEDGE *e;
PTREE *tree;
LELEMENT *current;
  /* return e's value for the attribute represented by the tree */
{
    int i;

    exec_ckp;

    if (tree == NULL)
    {
    exec_error = TRUE;
        print_cl(current);
    fprintf(stderr, "Edge attribute tree is empty.\n");
    return NULL;
    }
    else
    {
        switch(tree->token)
    {
        case STRING_TOKEN:
        for (i = 0; i < NEdgeAttr(digraph); i++)
        {
            if (!strcmp(tree->val, EAttrName(digraph, i)))
            {
            return EAttr(e, i);
            }
        }

        exec_error = TRUE;
        print_ln(tree->lineno);
            print_cl(current);
        fprintf(stderr, "No edge attribute named %s\n", tree->val);
        return NULL;
        case BRUSH_TOKEN:
        return brush_to_string(Brush(e));
        case COLOR_TOKEN:
        return brush_to_string(Color(e));
        case NODE_TOKEN:
        return bool_to_string(FALSE);
        case EDGE_TOKEN:
        return bool_to_string(TRUE);
        default:
        exec_error = TRUE;
        print_ln(tree->lineno);
            print_cl(current);
        fprintf(stderr, "Edge attribute tree cannot be rooted with ");
        print_token(tree->token, TRUE);
        return NULL;
    }
    }
}

create_nattr(digraph, name)
DIGRAPH *digraph;
char *name;
  /**
     create a new node attribute named name and initialize it to the NULL
     string for all nodes
   **/
{
    NODE *node;

    NNodeAttr(digraph)++;

    digraph->node_att_names =
    (char **) realloc((char *) digraph->node_att_names,
              (NNodeAttr(digraph)) * sizeof(char *));
    strsave(NAttrName(digraph, NNodeAttr(digraph) - 1), name);

    all_nodes(digraph, node)
    loop
    node->attributes =
        (char **) realloc((char *) node->attributes,
                  (NNodeAttr(digraph)) * sizeof(char *));
    strsave(NAttr(node, NNodeAttr(digraph) - 1), NULL_STRING);
    endloop;
}

create_eattr(digraph, name)
DIGRAPH *digraph;
char *name;
  /**
     Create a new edge attribute named name and initialize it to the NULL
     string for all edges
   **/
{
    NODE *node;
    OUTEDGE *edge;

    NEdgeAttr(digraph)++;

    digraph->edge_att_names =
    (char **) realloc((char *) digraph->edge_att_names,
              (NEdgeAttr(digraph)) * sizeof(char *));
    strsave(EAttrName(digraph, NEdgeAttr(digraph) - 1), name);

    all_nodes(digraph, node)
    loop
    all_out_edges(node, edge)
    loop
        edge->attributes =
            (char **) realloc((char *) edge->attributes,
                      (NEdgeAttr(digraph)) * sizeof(char *));
        strsave(EAttr(edge, NEdgeAttr(digraph) - 1), NULL_STRING);
    endloop;
    endloop;
}

BOOL get_bool_val(expr, digraph, current)
PTREE *expr;
DIGRAPH *digraph;
LELEMENT *current;
  /* all 'values' are actually strings for comparison's sake, even booleans */
{
    char *s;

    s = get_val(expr, digraph, current);
    exec_ckb;

    if (!strcmp(s, "true"))
    {
    return TRUE;
    }
    else if (!strcmp(s, "false"))
    {
        return FALSE;
    }
    else
    {
    exec_error = TRUE;
    print_ln(expr->lineno);
        print_cl(current);
    fprintf(stderr, "%s is not a boolean value.\n", s);
    return FALSE;
    }
}

LELEMENT *get_inedges(node, digraph)
NODE *node;
DIGRAPH *digraph;
  /**
     get the inedges of a node.  As noted elsewhere, some inedges are actually
     outedges and vice versa, so look at both lists
   **/
{
    LELEMENT *head, *curr, *c;

    head = NULL;

    curr = iedges(digraph, node);

    for (; curr != NULL; curr = c)
    {
    c = curr->next;

    if (!Edge_reversed((OUTEDGE *) curr->gelement))
    {
        curr->next = head;
        head = curr;
    }
    else
    {
       dispose(curr);
    }
    }

    curr = oedges(digraph, node);

    for (; curr != NULL; curr = c)
    {
    c = curr->next;

    if (Edge_reversed((OUTEDGE *) curr->gelement))
    {
        curr->next = head;
        head = curr;
    }
    else
    {
        dispose(curr);
    }
    }

    return head;
}

LELEMENT *get_outedges(node, digraph)
NODE *node;
DIGRAPH *digraph;
  /* get the outedges of a node.  The comment for get_inedges applies here */
{
    LELEMENT *head, *curr, *c;

    head = NULL;

    curr = oedges(digraph, node);

    for (; curr != NULL; curr = c)
    {
    c = curr->next;

    if (!Edge_reversed((OUTEDGE *) curr->gelement))
    {
        curr->next = head;
        head = curr;
    }
    else
    {
        dispose(curr);
    }
    }

    curr = iedges(digraph, node);

    for (; curr != NULL; curr = c)
    {
    c = curr->next;

    if (Edge_reversed((OUTEDGE *) curr->gelement))
    {
        curr->next = head;
        head = curr;
    }
    else
    {
        dispose(curr);
    }
    }

    return head;
}

LELEMENT *get_parents(node, digraph)
NODE *node;
DIGRAPH *digraph;
  /* get the parents of a node.  See the comment for get_inedges */
{
    LELEMENT *head, *curr, *c, *p;
    OUTEDGE *oe;
    SET *visited;
    NODE *tonode;

    head = NULL;
    init_set(visited);

    p = iedges(digraph, node);

    for (c = p; p != NULL; p = p->next)
    {
    oe = (OUTEDGE *) p->gelement;

    if (!in(visited, Vno(p->from)) && !Edge_reversed(oe))
    {
        add_element(visited, Vno(p->from));
        new(curr, LELEMENT);
        curr->node = TRUE;
        curr->gelement = (GELEMENT) (p->from);
        curr->from = NULL;
        curr->next = head;
        head = curr;
    }
    }

    dispose_lelem_list(c);
    p = oedges(digraph, node);

    for (c = p; p != NULL; p = p->next)
    {
    oe = (OUTEDGE *) p->gelement;
    tonode = visual(digraph, Node(digraph, To_vno(oe)));

    if (!in(visited, Vno(tonode)) && Edge_reversed(oe))
    {
        add_element(visited, Vno(tonode));
        new(curr, LELEMENT);
        curr->node = TRUE;
        curr->gelement = (GELEMENT) tonode;
        curr->from = NULL;
        curr->next = head;
        head = curr;
    }
    }

    dispose_lelem_list(c);
    dispose(visited);
    return head;
}

LELEMENT *get_children(node, digraph)
NODE *node;
DIGRAPH *digraph;
  /* get the children of a node.  See the comment for get_inedges */
{
    LELEMENT *head, *curr, *c, *p;
    OUTEDGE *oe;
    SET *visited;
    NODE *tonode;

    head = NULL;
    init_set(visited);

    p = oedges(digraph, node);

    for (c = p; p != NULL; p = p->next)
    {
    oe = (OUTEDGE *) p->gelement;
    tonode = visual(digraph, Node(digraph, To_vno(oe)));

    if (!in(visited, Vno(tonode)) && !Edge_reversed(oe))
    {
        add_element(visited, Vno(tonode));
        new(curr, LELEMENT);
        curr->node = TRUE;
        curr->gelement = (GELEMENT) tonode;
        curr->from = NULL;
        curr->next = head;
        head = curr;
    }
    }

    dispose_lelem_list(c);
    p = iedges(digraph, node);

    for (c = p; p != NULL; p = p->next)
    {
    oe = (OUTEDGE *) p->gelement;

    if (!in(visited, Vno(p->from)) && Edge_reversed(oe))
    {
        add_element(visited, Vno(p->from));
        curr->node = TRUE;
        curr->gelement = (GELEMENT) p->from;
        curr->from = NULL;
        curr->next = head;
        head = curr;
    }
    }

    dispose_lelem_list(c);
    dispose(visited);
    return head;
}

get_tc(node, digraph, visited, ppred, head)
NODE *node;
DIGRAPH *digraph;
SET *visited;
BOOL ppred;
LELEMENT **head;
  /**
     Find the transitive predecessor (if ppred is true) or successor (if pred
     is false) closure of the digraph from node.  A recursive procedure; the
     visited variable indicates if we've visited the node before.  head is
     a list of the nodes in the closure so far.

     Uses the depth-first search algorithm we know and love.

     See get_inedges for another detail
   **/
{
    LELEMENT *curr, *c, *p;
    NODE *neighbor;
    OUTEDGE *oe;

    p = oedges(digraph, node);

    for (c = p; p != NULL; p = p->next)
    {
    oe = (OUTEDGE *) p->gelement;
    neighbor = visual(digraph, Node(digraph, To_vno(oe)));

    if (!in(visited, Vno(neighbor)) && Edge_reversed(oe) == ppred)
    {
        add_element(visited, Vno(neighbor));

            new(curr, LELEMENT);
            curr->node = TRUE;
            curr->gelement = (GELEMENT) neighbor;
            curr->from = NULL;
            curr->next = *head;
            *head = curr;

        get_tc(neighbor, digraph, visited, ppred, head);
          /* recursion (whee!) */
    }
    }

    dispose_lelem_list(c);
    p = iedges(digraph, node);

    for (c = p; p != NULL; p = p->next)
    {
    oe = (OUTEDGE *) p->gelement;

    if (!in(visited, Vno(p->from)) && !Edge_reversed(oe) == ppred)
    {
        neighbor = p->from;
        add_element(visited, Vno(neighbor));

            new(curr, LELEMENT);
            curr->node = TRUE;
            curr->gelement = (GELEMENT) neighbor;
            curr->from = NULL;
            curr->next = *head;
            *head = curr;

        get_tc(neighbor, digraph, visited, ppred, head);
        /* recursion (whee!) */
    }
    }

    dispose_lelem_list(c);
}

LELEMENT *get_ancestors(node, digraph)
NODE *node;
DIGRAPH *digraph;
{
    SET *visited;
    LELEMENT *result = NULL;

    init_set(visited);
    get_tc(node, digraph, visited, TRUE, &result);
    dispose(visited);
    return result;
}

LELEMENT *get_descendants(node, digraph)
NODE *node;
DIGRAPH *digraph;
{
    SET *visited;
    LELEMENT *result = NULL;

    init_set(visited);
    get_tc(node, digraph, visited, FALSE, &result);
    dispose(visited);
    return result;
}

LELEMENT *get_source(edge, digraph, from)
OUTEDGE *edge;
DIGRAPH *digraph;
NODE *from;
  /* get the source of an edge.  Be sure to check if it's reversed */
{
    LELEMENT *result;

    new(result, LELEMENT);
    result->from = NULL;
    result->node = TRUE;
    result->next = NULL;

    if (Edge_reversed(edge))
    {
        result->gelement = (GELEMENT) visual(digraph,
                         Node(digraph, To_vno(edge)));
    }
    else
    {
        result->gelement = (GELEMENT) from;
    }

    return result;
}

LELEMENT *get_sink(edge, digraph, from)
OUTEDGE *edge;
DIGRAPH *digraph;
NODE *from;
  /* get the sink of an edge.  Be sure to check if it's reversed */
{
    LELEMENT *result;

    new(result, LELEMENT);
    result->from = NULL;
    result->node = TRUE;
    result->next = NULL;

    if (Edge_reversed(edge))
    {
    result->gelement = (GELEMENT) from;
    }
    else
    {
    result->gelement = (GELEMENT) visual(digraph,
                         Node(digraph, To_vno(edge)));
    }

    return result;
}

LELEMENT *all_nodes_edges(digraph)
DIGRAPH *digraph;
  /**
     make an lelement list of all the nodes and edges in the digraph
     we are concerned about
   **/
{
    NODE *node;
    LELEMENT *head, *curr;

    head = NULL;

    each_pred_node(digraph, node)
    loop
    if (Is_dummy(node))    /* don't care about dummies */
    {
        continue;
    }

    new(curr, LELEMENT);
    curr->node = TRUE;
    curr->gelement = (GELEMENT) node;
    curr->from = NULL;
    curr->next = head;
    head = curr;

        append_list_dups(oedges(digraph, node), &head);
                /* add relevant outedges */
    endloop;

    return head;
}

LELEMENT *oedges(digraph, inode)
DIGRAPH *digraph;
NODE *inode;
  /**
     Return an lelement list of all the outedges of inode
     inode may or may not be coalescer.
   **/
{
    VNO nvno;
    OUTEDGE *outedge;
    LELEMENT *curr, *result = NULL;
    NODE *to, *node;

    if (Coalescer(inode))
    {
    each_element(Expansion(inode), nvno)
    loop
        append_list_dups(oedges(digraph, Node(digraph, nvno)), &result);
    endloop;
    }
    else
    {
    all_out_edges(inode, outedge)
    loop
        to = visual(digraph, Node(digraph, To_vno(outedge)));
        node = visual(digraph, inode);
          /* get the visible endpoint of the edge */

        if (Displayed(to) || !ignoreHidden)
        {
            new(curr, LELEMENT);
            curr->node = FALSE;
            curr->gelement = (GELEMENT) outedge;
            curr->from = node;
            curr->next = result;
            result = curr;
        }
    endloop;
    }

    return result;
}

LELEMENT *iedges(digraph, node)
DIGRAPH *digraph;
NODE *node;
  /**
     Return an lelement list of all the outedges with inode as their
     to_vno.
     inode may or may not be coalescer.
   **/
{
    VNO nvno;
    INEDGE *inedge;
    LELEMENT *curr, *result = NULL;
    NODE *from, *ifrom;

    if (Coalescer(node))
    {
    each_element(Expansion(node), nvno)
    loop
        append_list_dups(iedges(digraph, Node(digraph, nvno)), &result);
    endloop;
    }
    else
    {
    all_in_edges(node, inedge)
    loop
        ifrom = Node(digraph, From_vno(inedge));
        from = visual(digraph, ifrom);

        if (Displayed(from) || !ignoreHidden)
        {
            new(curr, LELEMENT);
            curr->node = FALSE;
            curr->gelement = (GELEMENT) get_edge(digraph, ifrom, node,
                             Ord(inedge));
            curr->from = from;
            curr->next = result;
            result = curr;
        }
    endloop;
    }

    return result;
}

print_ln(n)
int n;
  /* prints a line number */
{
    fprintf(stderr, "on line #%d:  ", n);
}

print_cl(elem)
LELEMENT *elem;
  /* prints the label of the current node/edge */
{
    if (elem->node)
    {
    fprintf(stderr, "node \`%s\':  ", Text((NODE *) elem->gelement));
    }
    else
    {
    fprintf(stderr, "edge \`%s\':  ", Label((OUTEDGE *) elem->gelement));
    }
}

char **copy_attr();
VERTEX *insert_vertex();
NODE *insert_node();

coalesce(digraph, n1, n2)
DIGRAPH *digraph;
NODE *n1, *n2;
  /**
     coalesce n1 to n2 (n2 becomes the distinguished node)
   **/
{
    NODE *cr_node;
    VERTEX *cr_vertex;
    char name[MAXBUFFER];  /* name of the coalescer */
    char** attr;

    if (Coalescer(n2))
    {
    cr_node = n2;
    }
    else
    {
        strncpy(name, UniqueName(), MAXBUFFER);
        attr = copy_attr(n2->attributes, NNodeAttr(digraph));

          /* create a coalescer. */
        cr_vertex = insert_vertex(digraph, name);
        cr_node = insert_node(digraph, cr_vertex, attr, Shape(n2),
                          Brush(n2), Color(n2), Displayed(n2), 0, 0,
                 NORMAL);
    Coalescer(cr_node) = TRUE;
    add_to_coalescer(digraph, n2, cr_node);
    }

    if (n1 == cr_node)
    {
    return;        /* nop to add a coalesced node to itself */
    }

    add_to_coalescer(digraph, n1, cr_node);
}

add_to_coalescer(digraph, n, cn)
DIGRAPH *digraph;
NODE *n, *cn;
  /**
     add n to the coalescer node cn

     This doesn't work correctly; if n has edges to a coalescer node, the
     elements of that node must be changed so their ante/succ sets include
     cn instead of n.  This would cause troubles were the coalescer to
     be expanded.

     But, if that were to take place, you couldn't access the elements
     of the expansions in this set of predicates.  And after every set of
     predicates which include an expand, the ante/succ sets are recomputed
     (in relay.c).  So it works for now.

     To fix it, the remove_element, add_element calls would have
     to recurse for every element in the expansion if the neighbor
     were a coalescer.  But you also have to watch for hidden nodes.
     Which is why I leave it to relay.c
   **/
{
    VNO cr_vno, vno, succ_vno, ante_vno;  /* vertex numbers */

    cr_vno = Vno(cn);
    vno = Vno(n);
    Coalescer_vno(n) = cr_vno;   /* this node has a coalescer */
    Coalesced(n) = TRUE;
    Displayed(n) = FALSE;
    add_element(Expansion(cn), vno);

      /**
     add the successors and predecessors of this node to the coalescer
     node, but don't include elements in the coalescer node
       **/
    union(Succ_set(cn), Succ_set(n));
    union(Ante_set(cn), Ante_set(n));
    difference(Succ_set(cn), Expansion(cn));
    difference(Ante_set(cn), Expansion(cn));

    each_element(Succ_set(n), succ_vno)
      /* fix succedents to point to the coalescer */
    loop
    remove_element(Ante_set(Node(digraph, succ_vno)), vno);
    add_element(Ante_set(Node(digraph, succ_vno)), cr_vno);
    endloop

    each_element(Ante_set(n), ante_vno)
      /* fix antecedents to point to the coalescer*/
    loop
        remove_element(Succ_set(Node(digraph, ante_vno)), vno);
        add_element(Succ_set(Node(digraph, ante_vno)), cr_vno);
    endloop

      /* make sure the coalescer isn't its own successor or predecessor */
    remove_element(Succ_set(cn), cr_vno);
    remove_element(Ante_set(cn), cr_vno);
} /* add_to_coalescer */

expand(digraph, n1)
DIGRAPH *digraph;
NODE *n1;
  /**
     the inverse of coalescing.  n1 is a coalescer.  Break it up into
     its consituent parts

     Also doesn't quite get the ante/succ sets right.  See add_to_coalescer.

     Need to change the add_element calls below to also add nvno to
     the proper succ/ante sets if the neighbors are coalescer nodes.  And
     watch out for hidden nodes.  This is best left to relay.c
   **/
{
    VNO nvno, succ_vno, ante_vno, cr_vno;
    NODE *n;

    cr_vno = Vno(n1);

    each_element(Expansion(n1), nvno)
    loop
    n = Node(digraph, nvno);
    Coalescer_vno(n) = -1;
    Coalesced(n) = FALSE;
    Displayed(n) = TRUE;

          /**
         add this node back to the successor and predecessor set of its
         neighbors
       **/
        each_element(Succ_set(n), succ_vno)
        loop
        add_element(Ante_set(Node(digraph, succ_vno)), nvno);
        endloop

        each_element(Ante_set(n), ante_vno)
        loop
            add_element(Succ_set(Node(digraph, ante_vno)), nvno);
        endloop
    endloop;

      /**
     delete the coalescer node from the successor and predecessor
     sets of other nodes
       **/
    each_element(Succ_set(n1), succ_vno)
    loop
    remove_element(Ante_set(Node(digraph, succ_vno)), cr_vno);
    endloop;

    each_element(Ante_set(n1), ante_vno)
    loop
        remove_element(Succ_set(Node(digraph, ante_vno)), cr_vno);
    endloop

      /**
     if we don't set Coalescer to false, dispose_node will
     delete every element in the coalescer's expansion set
       **/
    Coalescer(n1) = FALSE;
    dispose_node(digraph, n1);
}

NODE *visual(digraph, n)
DIGRAPH *digraph;
NODE *n;
  /* find the coalescer node which represents n (if any) */
{
    while (Coalesced(n))
    {
    n = Node(digraph, Coalescer_vno(n));
    }

    return n;
}